#include "QvLzf.h"

QvUInt32 HLOG = 14;
QvUInt32 HSIZE = (1 << 14);

/*
* don't play with this unless you benchmark!
* decompression is not dependent on the hash function
* the hashing function might seem strange, just believe me it works ;)
*/
QvUInt32 MAX_LIT = (1 << 5);
QvUInt32 MAX_OFF = (1 << 13);
QvUInt32 MAX_REF = ((1 << 8) + (1 << 3));

//inline QvUInt32 FRST(const QvByte* Array, QvUInt32 nIndex)
//{
//    return (QvUInt32)(((Array[nIndex]) << 8) | Array[nIndex + 1]);
//}
#define FRST(Array, nIndex)  (QvUInt32)(((Array[nIndex]) << 8) | Array[nIndex + 1])

//inline QvUInt32 NEXT(QvUInt32 v, const QvByte* Array, QvUInt32 nIndex)
//{
//    return ((v) << 8) | Array[nIndex + 2];
//}
#define NEXT(v, Array, nIndex)   (((v) << 8) | Array[nIndex + 2])

//inline QvUInt32 IDX(QvUInt32 h)
//{
//    return ((h ^ (h << 5)) >> (int)(((3 * 8 - HLOG)) - h * 5) & (HSIZE - 1));
//}
#define IDX(h)  ((h ^ (h << 5)) >> (int)(((3 * 8 - HLOG)) - h * 5) & (HSIZE - 1))

QvLzf::QvLzf(void)
{
}

QvLzf::~QvLzf(void)
{
}

QvMemoryStream* QvLzf::Zip(QvDataArray<QvByte>* srcData)
{
    if(srcData)
    {
        return Zip(srcData->GetBuffer(), srcData->GetLength());
    }
    return NULL;
}

QvMemoryStream* QvLzf::UnZip(QvDataArray<QvByte>* srcData)
{
    if(srcData)
    {
        return UnZip(srcData->GetBuffer(), srcData->GetLength());
    }
    return NULL;
}

/*
* compressed format
*
* 000LLLLL <L+1>    ; literal
* LLLOOOOO oooooooo ; backref L
* 111OOOOO LLLLLLLL oooooooo ; backref L+7
*/
QvMemoryStream* QvLzf::Zip(const QvByte* srcData, QvUInt32 uLength)
{
    QvMemoryStream* zipStream = new QvMemoryStream();
    long htab[1 << 14];
    for (int c = 0; c < 1 << 14; c++)
    {
        htab[c] = 0;
    }
    long hslot = 0;
    QvUInt32 iidx = 0;
    long reference = 0;

    QvUInt32 hval = FRST(srcData, iidx);
    QvUInt32 off = 0;
    int lit = 0;

    for (; ; )
    {
        if (iidx < uLength - 2)
        {
            hval = NEXT(hval, srcData, iidx);
            hslot = IDX(hval);
            reference = htab[hslot];
            htab[hslot] = (long)iidx;

            if ((off = iidx - reference - 1) < MAX_OFF
                && iidx + 4 < uLength
                && reference > 0
                && srcData[reference + 0] == srcData[iidx + 0]
            && srcData[reference + 1] == srcData[iidx + 1]
            && srcData[reference + 2] == srcData[iidx + 2]
            )
            {
                /* match found at *reference++ */
                QvUInt32 len = 2;
                QvUInt32 maxlen = (QvUInt32)uLength - iidx - len;
                maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;

                do
                len++;
                while (len < maxlen && srcData[reference + len] == srcData[iidx + len]);

                if (lit != 0)
                {
                    zipStream->WriteByte((QvByte)(lit - 1));
                    lit = -lit;
                    do
                    zipStream->WriteByte(srcData[iidx + lit]);
                    while ((++lit) != 0);
                }

                len -= 2;
                iidx++;

                if (len < 7)
                {
                    zipStream->WriteByte((QvByte)((off >> 8) + (len << 5)));
                }
                else
                {
                    zipStream->WriteByte((QvByte)((off >> 8) + (7 << 5)));
                    zipStream->WriteByte((QvByte)(len - 7));
                }

                zipStream->WriteByte((QvByte)off);

                iidx += len - 1;
                hval = FRST(srcData, iidx);

                hval = NEXT(hval, srcData, iidx);
                htab[IDX(hval)] = iidx;
                iidx++;

                hval = NEXT(hval, srcData, iidx);
                htab[IDX(hval)] = iidx;
                iidx++;
                continue;
            }
        }
        else if (iidx == uLength)
            break;

        /* one more literal byte we must copy */
        lit++;
        iidx++;

        if (lit == MAX_LIT)
        {
            zipStream->WriteByte((QvByte)(MAX_LIT - 1));
            lit = -lit;
            do
            zipStream->WriteByte(srcData[iidx + lit]);
            while ((++lit) != 0);
        }
    }

    if (lit != 0)
    {
        zipStream->WriteByte((QvByte)(lit - 1));
        lit = -lit;
        do
        zipStream->WriteByte(srcData[iidx + lit]);
        while ((++lit) != 0);
    }
    zipStream->SetCursorAt(0);
    return zipStream;
}

QvMemoryStream* QvLzf::UnZip(const QvByte* srcData, QvUInt32 uLength)
{
    QvMemoryStream* unzipStream = new QvMemoryStream();
    QvUInt32 iidx = 0;
    QvUInt32 oidx = 0;
    do
    {
        QvUInt32 ctrl = srcData[iidx++];

        if (ctrl < (1 << 5)) /* literal run */
        {
            ctrl++;

            do
            {
                oidx++;
                unzipStream->WriteByte(srcData[iidx++]);
            } while ((--ctrl) != 0);
        }
        else /* back reference */
        {
            QvUInt32 len = ctrl >> 5;

            int reference = (int)(oidx - ((ctrl & 0x1f) << 8) - 1);

            if (len == 7)
                len += srcData[iidx++];

            reference -= srcData[iidx++];

            if (reference < 0)
            {
                unzipStream->Release();
                return NULL;
            }
            unzipStream->WriteByte(unzipStream->GetBuffer()[reference++]);
            oidx++;
            unzipStream->WriteByte(unzipStream->GetBuffer()[reference++]);
            oidx++;

            do
            {
                unzipStream->WriteByte(unzipStream->GetBuffer()[reference++]);
                oidx++;
            } while ((--len) != 0);
        }
    }
    while (iidx < uLength);
    unzipStream->SetCursorAt(0);
    return unzipStream;
}
